package cn.algorithms_4ed.algo.union_find;

import cn.stdlib.In;
import cn.stdlib.StdOut;

/**
 * 加权 quick-union
 * <p/>
 * User: erhu
 * Date: 13-6-12
 * Time: 下午9:55
 */
public class UFWeightedQuickUnionUF extends UFQuickFind {

    int[] sz;

    public UFWeightedQuickUnionUF(int _size) {
        super(_size);
        sz = new int[_size];
        for (int i = 0; i < _size; i++)
            sz[i] = 1;
    }

    @Override
    protected void union(int p, int q) {
        int p_root = find(p);
        int q_root = find(q);

        if (p_root == q_root)
            return;

        // p 所在树是小树 => 将小树的根接到大树的根
        if (sz[p_root] < sz[q_root]) {
            id[p] = q_root;
            sz[q_root] += sz[p_root];
        } else {
            id[q] = p_root;
            sz[p_root] += sz[q_root];
        }

        count--;
    }

    public static void main(String[] args) {
        long begin = System.currentTimeMillis();

        String file_medium = "/Users/erhu/Dropbox/workspace/java-study/algs4-data/mediumUF.txt";
        String file_large = "/Users/erhu/w-dev/largeUF.txt";

        In in = new In(file_large);
        int N = in.readInt();

        UFWeightedQuickUnionUF uf = new UFWeightedQuickUnionUF(N);
        while (!in.isEmpty()) {
            int p = in.readInt();
            int q = in.readInt();
            if (uf.collected(p, q)) {
                continue;
            }
            uf.union(p, q);
            //StdOut.println(p + " " + q);
        }
        StdOut.print(uf.count() + " components.");

        StdOut.println("time: " + ((System.currentTimeMillis() - begin) / 1000.0));
    }
}
